package com.cty.sortAlgorithms;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 *
 *
 * 基数排序
 *
 *
 * */
public class RadixSort {
    public static void main(String[] args) {
        int [] arr = {569,157,55,3,7};
        radixSort(arr);
        System.out.println("排序后的数组:" + Arrays.toString(arr));
        int[] arr2 = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr2[i] = (int) (Math.random() * 8000000);
        }
        //实际计算一下基数算法所需要的时间
        Date date1 = new Date();
        //格式化一下时间
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String format1 = simpleDateFormat.format(date1);
        System.out.println(format1);
        radixSort(arr2);
        Date date2 = new Date();
        String format2 = simpleDateFormat.format(date2);
        System.out.println(format2);//1秒不到
    }
    public static void radixSort(int[] arr) {
        //首先获得基数排序中最大的值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //获得基数排序中最大值的位数(决定接下来循环几次)
        int maxLength = (max + "").length();
        //创建需要的10个桶
        int[][] bucket = new int[10][arr.length];
        //作用：数组下标代表第几个桶，对应的值代表桶中有几个数据
        int[] bucketCount = new int[10];
        //数位
        int bit;
        for (int i = 0,n = 1;i < maxLength;i++,n *= 10) {
            //先循环将数据装入桶
            for (int j = 0;j < arr.length;j++) {
                bit = arr[j] / n % 10;
                bucket[bit][bucketCount[bit]] = arr[j];
                bucketCount[bit]++;
            }
            //装入桶中之后将数据取出
            int index = 0;//用于从桶中取出数据时用的索引
            for (int k = 0;k < bucketCount.length;k++) {
                if (bucketCount[k] > 0) {
                    for (int l = 0;l < bucketCount[k];l++) {
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //将桶中的索引制为零，以表示数据全取出
                bucketCount[k] = 0;
            }
        }
    }
}
